package main.leetcode.primary.from901to1000;

/**
 * 956. 最高的广告牌
 *
 * <p>你正在安装一个广告牌，并希望它高度最大。这块广告牌将有两个钢制支架，两边各一个。每个钢支架的高度必须相等。
 *
 * <p>你有一堆可以焊接在一起的钢筋 rods。举个例子，如果钢筋的长度为 1、2 和 3，则可以将它们焊接在一起形成长度为 6 的支架。
 *
 * <p>返回广告牌的最大可能安装高度。如果没法安装广告牌，请返回 0。
 *
 * <p>示例 1：输入：[1,2,3,6] 输出：6 解释：我们有两个不相交的子集 {1,2,3} 和 {6}，它们具有相同的和 sum = 6。
 *
 * <p>示例 2：输入：[1,2,3,4,5,6] 输出：10 解释：我们有两个不相交的子集 {2,3,5} 和 {4,6}，它们具有相同的和 sum = 10。
 *
 * <p>示例 3：输入：[1,2] 输出：0 解释：没法安装广告牌，所以返回 0。
 *
 * <p>提示：0 <= rods.length <= 20，1 <= rods[i] <= 1000，钢筋的长度总和最多为 5000
 */
public class ex956 {
    //    private int res;

    private static int res = Integer.MAX_VALUE;

    public static void main(String[] args) {
        System.out.println(new ex956().tallestBillboard(new int[] {1, 2, 3, 6}));
        System.out.println(new ex956().tallestBillboard(new int[] {1, 2, 3, 4, 5, 6}));
        System.out.println(
                new ex956()
                        .tallestBillboard(
                                new int[] {
                                    1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 50, 50, 50, 150, 150,
                                    150, 100, 100, 100, 123
                                }));
    }

    private int tallestBillboard(int[] nums) {
        int n = nums.length;
        // 后缀和
        int[] suffix = new int[n + 1];
        for (int i = n - 1; i >= 0; --i) {
            suffix[i] = nums[i] + suffix[i + 1];
        }
        dfs(nums, suffix, 0, 0, 0, 0);
        return suffix[0] - res >> 1;
    }

    /** dfs枚举 */
    private void dfs(int[] nums, int[] suffix, int start, int val1, int val2, int cost) {
        // 更新
        if (val1 == val2) {
            res = Math.min(res, cost + suffix[start]);
        }
        // 递归尽头 || 剪枝
        if (start == nums.length || cost > res) {
            return;
        }
        // 枚举
        dfs(nums, suffix, start + 1, val1 + nums[start], val2, cost); // 分给1
        dfs(nums, suffix, start + 1, val1, val2 + nums[start], cost); // 分给2
        dfs(nums, suffix, start + 1, val1, val2, cost + nums[start]); // 丢弃
    }

    //    /** dfs */
    //    public int tallestBillboard(int[] rods) {
    //        if (rods == null || rods.length < 2) {
    //            return 0;
    //        }
    //        int sum = 0;
    //        for (int rod : rods) {
    //            sum += rod;
    //        }
    //        dfs(rods, rods.length - 1, 0, 0, sum);
    //        return res;
    //    }
    //
    //    private void dfs(int[] rods, int start, int x, int y, int remain) {
    //        if (x == y && x > res) {
    //            res = x;
    //        }
    //        if (start == rods.length || x + y + remain <= res * 2 || Math.abs(x - y) > remain) {
    //            return;
    //        }
    //        remain -= rods[start];
    //        dfs(rods, start - 1, x + rods[start], y, remain);
    //        dfs(rods, start - 1, x, y + rods[start], remain);
    //        dfs(rods, start - 1, x, y, remain);
    //    }

}
